package 贪心算法;

import java.util.Arrays;
import java.util.Comparator;

public class 无重叠区间_435 {

    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;

        //求出有n个区间不会重叠，剩下的区间就是需要去除的。
        return n - intervals(intervals);
    }

    /**
     * 最多有n个 区间不会重叠
     *
     * @param intervals
     * @return
     */
    public int intervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            //按照end升序排列
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        //至少有一个区间不相交,就是只有一个区间的时候
        int count = 1;
        //排序后第一个区间就是x
        int x_end = intervals[0][1];

        for (int[] interval : intervals) {
            int start = interval[0];
            if (start >= x_end) {
                //找到下一个选择的区间了
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }
}
